﻿#pragma once
#include<iostream>
#include<fstream>
#include <vector>
#include <set>
#include <unordered_map>
#include <map>
#include <list>
//#include <fstream>
#include "LR1TableGenerator.h"
#include "OLEX.h"

//using namespace std;

namespace LR1TableGeneratorNameSpace {//begin LR1TableGeneratorNameSpace



	void LR1TableGenerator::getGram(GRMLEX &gramConvertNum) {
		//1、将字串文法转换为数字代号文法
		//-----------------------------------------------------
		std::wcout.imbue(std::locale("chs"));
		std::wcin.imbue(std::locale("chs"));//对wstring的输入输出设定中文环境
		wstring gramIn;						//输入的文法A->BC的形式 A可以是字符、中文串、用""括起的字符串 
						//对输入的文法转化为数字串，其中	1代表增广文法的S' 2代表->	3代表|	4代表~空字
		vector<vector<GRAM_ELEMENT_TYPE>> gramNum;		//转化为数字后的文法
		while (getline(wcin, gramIn)) {
			//wcout << gramIn << endl;
			gramConvertNum.Analyses(gramIn);
		}
		gramNum = gramConvertNum.GetData();

		//2、文法转换数字完成，对文法进行处理
		//-----------------------------------------------------
		LR1TableGenerator::gramList;//使用到的类内部成员
		LR1TableGenerator::vnFirst;
		LR1TableGenerator::vtFirst;
		vector<GRAM_ELEMENT_TYPE> v;             //当前的产生式
		int ch;                    //当前产生式中的字符
		int ptr = 0;                  //当前行读取的第i个字符
		int X;                     //当前产生式的左侧符号，用于分解A->a|b|c为A->a A->b A-c
		set<GRAM_ELEMENT_TYPE> m;
		vnFirst[1] = m;                //增广文法，把1作为初始非终结符

		for (int i = 0; i < gramNum.size(); i++) {//遍历文法元素
			for (int j = 0; j < gramNum[i].size(); j++) {

				if (gramNum[i][j] == CHAR_OR) { //消除语言符号'|'	(CHAR_OR代表‘|’)
					gramList.push_back(v);
					v.clear();
					ptr = 2;//重新定位到“->”上，I++后移动到产生式右部
					v.push_back(X);
					continue;
				}
				ptr++;
				if (ptr == 1) {
					X = gramNum[i][j];
					vnFirst[X] = m; //产生式左边(第一个字符)的为非终结符
				}
				else if (ptr != 2 && gramNum[i][j] != CHAR_NULL) vtFirst[gramNum[i][j]] = m; //此时vtFirst里既有非终结符又有终结符

				if (ptr != 2)v.push_back(gramNum[i][j]); //去掉产生式的->

			}

			if (!v.empty()) gramList.push_back(v);  //换行时，缓冲区中非空，则写入gramList
			v.clear();
			ptr = 0;

		}

		if (gramList.empty()) exit(0);

		//3、增广文法。加入新树根M 在gramList头部插入增广文法产生式
		//-----------------------------------------------------
		v.clear();
		v.push_back(1);
		v.push_back(gramList[0][0]);
		gramList.insert(gramList.begin(), v);

		//4、去掉vtFirst中的非终结符
		//-----------------------------------------------------
		for (unordered_map<GRAM_ELEMENT_TYPE, set<GRAM_ELEMENT_TYPE> >::iterator it = vnFirst.begin(); it != vnFirst.end(); it++) {//从vtFirst中删去vnFirst的元素
			unordered_map<GRAM_ELEMENT_TYPE, set<GRAM_ELEMENT_TYPE> >::iterator iter;
			iter = vtFirst.find(it->first);
			if (iter != vtFirst.end()) vtFirst.erase(iter);//   find没找到，返回unordered_map::end
		}

	}

	void LR1TableGenerator::showGram() {
		cout << "原文法增广为文法G[M]：" << endl;
		for (unsigned int i = 0; i < gramList.size(); i++) { //输出G'[S']
			cout << i << "）";
			for (unsigned int j = 0; j < gramList[i].size(); j++) {
				if (j == 1)cout << "->";
				if (j > 1)cout << " ";
				cout << gramList[i][j];
			}
			cout << endl;
		}
		cout << "终结符：" << endl;
		for (auto& it : vtFirst) {
			cout << it.first << endl;
		}
		cout << "非终结符：" << endl;
		for (auto& it : vnFirst) {
			cout << it.first << endl;
		}

	}

	void LR1TableGenerator::showFirst() {
		for (auto it1 : vtFirst) {
			cout << it1.first << ": ";
			for (auto it2 : it1.second) {
				cout << it2 << ",";
			}
			cout << endl;
		}
		cout << endl << endl;
		for (auto it1 : vnFirst) {
			cout << it1.first << ": ";
			for (auto it2 : it1.second) {
				cout << it2 << ",";
			}
			cout << endl;
		}
		cout << endl << endl;
	}

	void LR1TableGenerator::outputClosure() {
		fstream f("Closure.txt", ios::out);
		if (!f) {
			cout << "Closure.txt文件打开出错！" << endl;
			return;
		}
		f << "该文法的项目集和GO函数：" << endl;
		for (unsigned int i = 0; i < closureList.size(); i++) {
			f << "I" << i << ":" << endl;
			for (unsigned int j = 0; j < closureList[i].projectList.size(); j++) {
				for (unsigned int k = 0; k < closureList[i].projectList[j].size(); k++) {
					if (k == 1) f << "->";
					if (closureList[i].projectList[j][k] == CHAR_POINT) f << "·";
					else f << closureList[i].projectList[j][k] << " ";
				}
				f << "，";
				for (auto it : closureList[i].outlook[j]) {
					if (it == *(closureList[i].outlook[j].begin())) f << it;
					else f << "/" << it;
				}
				f << endl;
			}
			for (auto it : closureList[i].go) {
				f << "GO(I" << i << "，" << it.first << ") = I" << it.second << endl;
			}
			f << endl;
		}
		f.close();
		cout << "已将项目集和GO函数生成到Closure.txt文件中。" << endl << endl;
	}
	void LR1TableGenerator::outputLR1Table() {
		fstream f("LR_Table.txt", ios::out);
		if (!f) {
			cout << "LR_Table.txt文件打开出错！" << endl;
			return;
		}
		for (int i = -1; i < (int)closureList.size(); i++) {
			if (i == -1) f << " " << '\t';
			else f << i << '\t';
			for (auto it : vtFirst) {
				if (i == -1) f << it.first << '\t';
				else {
					map<string, GRAM_ELEMENT_TYPE> m;
					m[to_string(i)] = it.first;
					f << table[m] << '\t';
				}
			}
			if (i == -1) f << "#" << '\t';
			else {
				map<string, GRAM_ELEMENT_TYPE> m;
				m[to_string(i)] = CHAR_END;
				f << table[m] << '\t';
			}
			for (auto it : vnFirst) {
				if (it.first == CHAR_ORIGIN) continue;
				if (i == -1)f << it.first << '\t';
				else {
					map<string, GRAM_ELEMENT_TYPE> m;
					m[to_string(i)] = it.first;
					f << table[m] << '\t';
				}
			}
			f << endl;
		}
		f.close();
		cout << "已将LR分析表生成到LR_Table.txt文件中。" << endl << endl;
	}

	void LR1TableGenerator::generateFirst() {
		for (auto& it : vtFirst) it.second.insert(it.first);//终结符的first集合是它自己  //c++11用法 范围for循环

		//求非终结符的First集合
		int r = 0;
		bool change = true;
		while (change) {
			if (r == 20) { cout << " function \"generateFirst()\" has been running too long" << endl; 
				break;
			}
			r++;
			change = false;
			for (auto& curVn : vnFirst) { //对每个非终结符
				for (unsigned int i = 0; i < gramList.size(); i++) { //遍历产生式
					if (gramList[i][0] == curVn.first) {
						unsigned int size = curVn.second.size(); //操作前First(X)的大小
						unordered_map<GRAM_ELEMENT_TYPE, set<GRAM_ELEMENT_TYPE> >::iterator iter = vtFirst.find(gramList[i][1]);
						if (vtFirst.find(gramList[i][1]) != vtFirst.end() || gramList[i][1] == CHAR_NULL) { //形如X->a……或X->空字，把a或空字加入First(X)中
							curVn.second.insert(gramList[i][1]);
							if (curVn.second.size() > size) change = true;//利用set的性质，如果操作前后不相同，则标记first改变
						}
						else {  //形如X->Y……，把First(Y)加入First(X)
							unsigned int col = 1;
							while (1) { //若X->Y1Y2……,循环把First(Y)加入First(X)
								bool flag = false; //标记当前First(Y)中是否有空字
								unordered_map<GRAM_ELEMENT_TYPE, set<GRAM_ELEMENT_TYPE> >::iterator itt = vnFirst.find(gramList[i][col]);//itt指向Y的first集合
								for (auto& iter : itt->second) { //遍历First(Y)
									if (iter == CHAR_NULL) flag = true;
									else curVn.second.insert(iter);//把Y的FIRST集元素依次加入到当前非终结符的First集中
								}
								if (flag) {//如果当前指向的Y含空字产生式，则继续移向下一个Y
									col++;
									if (gramList[i].size() <= col) {//根据col得出的空非终结符的数量等于产生式右侧非终结符数量（也就是X->YZW```每一个都能推到空字）同时结束循环
										curVn.second.insert(CHAR_NULL); //将空字加入First(X)
										break;
									}
									else if (vtFirst.find(gramList[i][col]) != vtFirst.end()) { //形如X->Ya……，将a加入First(X) 遇到终结符，则结束循环
										curVn.second.insert(gramList[i][col]);
										break;
									}
									else { //形如X->YZ……，将First(Z)加入First(X)  继续循环下一个col
									}
								}
								else break;
							}
							if (curVn.second.size() > size) change = true;
						}
					}
				}
			}
		}
	}

	void LR1TableGenerator::generateClosure() {
		closure clo; //生成第一个闭包（I0）
		closureList.push_back(clo);
		bool closureChange = true;
		while (closureChange) {
			int i = 0; //闭包编号
			closureChange = false;
			vector <closure> closureListTemp = closureList;
			while (1) {
				if (i % 100 == 0) {
					outputClosure();
					cout << i << endl;
					//system("pause");
				}
				if (i == closureList.size()) break; //没有新闭包，跳出循环（即已获得全部闭包及项目）
				if (i == 0&& closureList.size()==1) { //确定项目集I0的第一个项目
					vector<GRAM_ELEMENT_TYPE> v(gramList[0]);
					v.insert(v.begin() + 1, CHAR_POINT);////////////////////////////////////
					closureList[i].projectList.push_back(v);
					set<GRAM_ELEMENT_TYPE> m;
					m.insert(CHAR_END);//////////////////////////
					closureList[i].outlook.push_back(m);
				}

				bool outLookChange = true;
				while (outLookChange) {
					outLookChange = false;
					vector< set<GRAM_ELEMENT_TYPE> > outlookTemp = closureList[i].outlook;

					for (unsigned int j = 0; j < closureList[i].projectList.size(); j++) {  //遍历已有项目，生成该闭包所有项目
						for (long long unsigned int pointPtr = 0; pointPtr < closureList[i].projectList[j].size(); pointPtr++) {  //扫描单个项目，找到当前位置·（这里用CHAR_POINT代替）
							if (closureList[i].projectList[j][pointPtr] == CHAR_POINT) {
								//-----------------------------------------------------------------------------------------------
								if (pointPtr < closureList[i].projectList[j].size() - 1) {//空字处理 
									if (closureList[i].projectList[j][pointPtr + 1] == CHAR_NULL) {//形如X->·~
										closureList[i].projectList[j][pointPtr] = CHAR_NULL;		//变为X->~·
										closureList[i].projectList[j][pointPtr + 1] = CHAR_POINT;
										pointPtr++;//k指向·
									}
								}
								//break;
								//-----------------------------------------------------------------------------------------------
								if (pointPtr == closureList[i].projectList[j].size() - 1) break;  //形如X->β·，不会生成新的项目

								for (unsigned int x = 0; x < gramList.size(); x++) { //形如X->α·Yβ，  遍历G'[M]，查找所有对应的产生式，以求出新的项目并加入项目集
									if (gramList[x][0] == closureList[i].projectList[j][pointPtr + 1]) { //找到·后Y的产生式
										vector<GRAM_ELEMENT_TYPE> v(gramList[x]); //用于保存新项目
										v.insert(v.begin() + 1, CHAR_POINT); //新项目把·放在右侧第一位
										//----------------------------------------------------------------------------------
										for (int l = 0; l < v.size() - 1; l++) {
											if (v[l] == CHAR_POINT && v[l + 1] == CHAR_NULL) {
												v[l] = CHAR_NULL;		//变为X->~·
												v[l + 1] = CHAR_POINT;
												break;
											}
										}
										//----------------------------------------------------------------------------------
										int exist = 0; //标记该新项目是否已存在
										for (unsigned int y = 0; y < closureList[i].projectList.size(); y++) { //遍历已有项目，判断是新项目还是已有项目
											if (closureList[i].projectList[y] == v) { //已有项目，只需保存项目下标（用于添加新的展望串）
												exist = y;
												break;
											}
										}
										if (exist == 0) closureList[i].projectList.push_back(v); //新项目，加入项目集

										set<GRAM_ELEMENT_TYPE> m; //用于保存新展望串
										//形如【形如X->α·Yβ，a】，计算展望串，即计算First(βa)
										//情况一：β为空字，First(βa)=a
										//情况二：β中第一个字符为终结符b，First(βa)=b
										//情况三：β中第一个字符为非终结符B，若First(B)中没有空字，First(βa)=First(B)；
										//                                   若First(B)中包含空字，First(βa)=First(B)+First(γa)，其中γ为β除去第一个字符B后形成的符号串
										bool kong = true; //标记情况三B中是否有空字
										int skipNum = 0; //表示当前符号串γ为β除去第skipNum个字符,跳过几个字符
										while (kong) { //若为情况三且B含空字，计算First(γa)
											kong = false;
											if (pointPtr + skipNum + 1 == closureList[i].projectList[j].size() - 1) {  //情况一(pointPtr + 1)为·后第一个字符）（closureList[i].project[j].size() - 1 为最后一个字符）
												for (auto it : closureList[i].outlook[j]) m.insert(it);//把当前项的所有展望，都加入到m中
											}
											else if (vtFirst.find(closureList[i].projectList[j][pointPtr + skipNum + 2]) != vtFirst.end()) {  //情况二
												m.insert(closureList[i].projectList[j][pointPtr + 2 + skipNum]);
											}
											else {  //情况三
												set<GRAM_ELEMENT_TYPE> m1((vnFirst.find(closureList[i].projectList[j][pointPtr + 2 + skipNum]))->second);
												for (auto it : m1) {
													if (it == CHAR_NULL) {  //含空字
														kong = true;
														skipNum++;
													}
													else { //不含空字
														m.insert(it);
													}
												}
											}
										}
										if (exist) //已存在项目，将新展望串加入原展望串中
										{
											for (auto it : m) {
												closureList[i].outlook[exist].insert(it);
											}
										}
										else closureList[i].outlook.push_back(m); //新项目，新展望串加入展望串集
									}
								}
								break;
							}
						}
					}//for循环  遍历closure i的每个项目
					if (outlookTemp.size() != closureList[i].outlook.size()) {
						//cout << "change outside" << endl;
						outLookChange = true;
					}
					else {
						for (int x = 0; x < outlookTemp.size() - 1; x++) {
							if (outlookTemp[x].size() != closureList[i].outlook[x].size()) {
								//cout << "change inside" << x << endl;
								outLookChange = true;
								break;
							}

						}
					}
				}
				//////////////////////////////////////////////////////////////////////////////
				//if (closureList.size() >= 6) {
				//	cout << i << "  CLOSURE" << endl;
				//	int x = 6;
				//	for (unsigned int j = 0; j < closureList[x].projectList.size(); j++) {
				//		for (unsigned int k = 0; k < closureList[x].projectList[j].size(); k++) {
				//			if (k == 1) cout << "->";
				//			if (closureList[x].projectList[j][k] == CHAR_POINT) cout << "·";
				//			else cout << closureList[x].projectList[j][k] << " ";
				//		}
				//		cout << "，";
				//		for (auto it : closureList[x].outlook[j]) {
				//			if (it == *(closureList[x].outlook[j].begin())) cout << it;
				//			else cout << "/" << it;
				//		}
				//		cout << endl;
				//	}
				//}
				//////////////////////////////////////////////////////////////////////////////

				for (unsigned int j = 0; j < closureList[i].projectList.size(); j++) {  //遍历本闭包的所有项目，计算GO函数，并生成新的闭包
					for (long long unsigned int pointPtr = 0; pointPtr < closureList[i].projectList[j].size(); pointPtr++) {  //扫描单个项目，找到当前位置·（这里用CHAR_NULL代替）
						if (closureList[i].projectList[j][pointPtr] == CHAR_POINT) {
							if (pointPtr == closureList[i].projectList[j].size() - 1) break; //形如【X->β·】，不会生成新闭包
							//计算GO函数，并生成新的闭包
							vector<GRAM_ELEMENT_TYPE> newClosureProject(closureList[i].projectList[j]); //用于保存新项目
							newClosureProject[pointPtr] = newClosureProject[pointPtr + 1]; //计算新项目
							newClosureProject[pointPtr + 1] = CHAR_POINT;						//交换·与其后元素的位置  此时会产生形如X->α·Yβ到 X->αY·β的go
							set<GRAM_ELEMENT_TYPE> newClosureOutlook(closureList[i].outlook[j]); //用于保存新展望串
							bool dif = false; //标记 生成的新项目是否属于已有的闭包（判断是否需生成新闭包）
							for (unsigned int x = 0; x < closureList.size(); x++) { //遍历已有闭包
								for (unsigned int y = 0; y < closureList[x].projectList.size(); y++) { //将新项目和新展望串与已有闭包的所有项目比较，若相同，则属于已有闭包，无需生成新闭包
									dif = false;
									if (newClosureProject == closureList[x].projectList[y]) {
										if (closureList[x].outlook[y].size() != newClosureOutlook.size()) { //比较展望串长
											dif = true;
											continue;
										}
										auto iter = closureList[x].outlook[y].begin();
										for (auto it : newClosureOutlook) {  //比较展望串每个字符
											if (it != *iter) {
												dif = true;
												break;
											}
											iter++;
										}
										if (dif == false) { //属于已有闭包，只计算GO函数
											if (closureList[i].go.count(newClosureProject[pointPtr]) == 0) {
												closureList[i].go[newClosureProject[pointPtr]] = x;
												break;
											}
										}
									}
									else dif = true;
									if (dif == false) break;
								}
								if (dif == false) break;
							}
							//由于pointPtr把·和·后元素换位，而pointPtr没有变，此时pointPtr指向换位前·后元素
							if (closureList[i].go.count(newClosureProject[pointPtr]) != 0 && dif) { //若有多个形如【X->α·Yβ】的产生式(相互不一样)，它们有同一GO函数(即属于同一闭包)，但生成的新项目不一样
								closureList[closureList[i].go[newClosureProject[pointPtr]]].projectList.push_back(newClosureProject); //只需将新项目及新展望串加入GO对应的闭包
								closureList[closureList[i].go[newClosureProject[pointPtr]]].outlook.push_back(newClosureOutlook);
								break;
							}
							if (dif) { //不属于已有闭包，生成新闭包，并计算GO函数
								closure newClosure;
								newClosure.projectList.push_back(newClosureProject);
								newClosure.outlook.push_back(newClosureOutlook);
								closureList.push_back(newClosure);
								closureList[i].go[newClosureProject[pointPtr]] = closureList.size() - 1;//指向新插入的closure
							}
						}
					}
				}//for循环，遍历项目，生成go
				//////////////////////////////////////////////////////////////////////////////
				//if (closureList.size() >= 6) {
				//	cout << i << "  GO" << endl;
				//	int x = 6;
				//	for (unsigned int j = 0; j < closureList[x].projectList.size(); j++) {
				//		for (unsigned int k = 0; k < closureList[x].projectList[j].size(); k++) {
				//			if (k == 1) cout << "->";
				//			if (closureList[x].projectList[j][k] == CHAR_POINT) cout << "·";
				//			else cout << closureList[x].projectList[j][k] << " ";
				//		}
				//		cout << "，";
				//		for (auto it : closureList[x].outlook[j]) {
				//			if (it == *(closureList[x].outlook[j].begin())) cout << it;
				//			else cout << "/" << it;
				//		}
				//		cout << endl;
				//	}
				//}
				//////////////////////////////////////////////////////////////////////////////

				i++; //下一闭包
			}
			if (closureListTemp.size() == closureList.size()) {
				for (int x = 0; x < closureList.size(); x++) {
					//		for(int y=0;y< closureList[x].projectList.size();y++)
					if (closureListTemp[x].projectList.size() != closureList[x].projectList.size()) {
						closureChange = true;
						break;
					}
				}
			}
			else
				closureChange = true;
		}
	}

	int LR1TableGenerator::generateTable() {
		for (unsigned int i = 0; i < closureList.size(); i++) { //遍历所有闭包
			for (unsigned int j = 0; j < closureList[i].projectList.size(); j++) { //遍历每个闭包中的所有项目
				for (unsigned int k = 0; k < closureList[i].projectList[j].size(); k++) { //扫描该项目,找到当前位置
					if (closureList[i].projectList[j][k] == CHAR_POINT) {
						//cout << 1 << endl;
						if (k == closureList[i].projectList[j].size() - 1) { //形如 【X->α·，β】，归约/acc
							if (closureList[i].projectList[j][0] == CHAR_ORIGIN) {  //形如 【M->X·，#】，令table[i,#]=acc
								map<string, GRAM_ELEMENT_TYPE> m;
								m[to_string(i)] = CHAR_END;
								if (table.find(m) != table.end() && table[m] != "acc") {
									cout << "该文法不是LR(1)文法，存在多重定义入口！" << endl;
									cout << "状态" << i << "+" << "符号" << CHAR_END << "->acc" << endl;
									cout << "状态" << i << "+" << "符号" << CHAR_END << "->" + table[m] << "\t二者冲突" << endl;
									//return 0;
								}
								else table[m] = "acc";
							}
							else { //形如 【X->α·，a】，归约，令table[i,a]=rj
								int id;
								for (unsigned int x = 0; x < gramList.size(); x++) { //扫描G'[M]找到对应的产生式的编号
									vector<GRAM_ELEMENT_TYPE> v(closureList[i].projectList[j]);
									v.pop_back();//去掉最后一位，如果是X->α·，则会和gramList中产生式相同
									if (gramList[x] == v) {
										id = x;
										break;
									}
								}
								for (auto it : closureList[i].outlook[j]) {
									map<string, GRAM_ELEMENT_TYPE> m;
									m[to_string(i)] = it;//最后一个展望符
									if (table.find(m) != table.end() && table[m] != (string)"r" + to_string(id)) {//令table[i,a]=rj
										cout << "该文法不是LR(1)文法，存在多重定义入口！" << endl;
										cout << "状态" << i << "+" << "符号" << it << "->" + (string)"r" + to_string(id) << endl;
										cout << "状态" << i << "+" << "符号" << it << "->" + table[m] << "\t二者冲突" << endl;
										//return 0;
									}
									else table[m] = (string)"r" + to_string(id);
								}
							}
						}
						else { //形如 【X->α·β，γ】
							int next = closureList[i].projectList[j][k + 1];
							if (vtFirst.find(next) != vtFirst.end()) {  //形如 【X->α·aβ，γ】,令table[i,a]=sj
								map<string, GRAM_ELEMENT_TYPE> m;
								m[to_string(i)] = next;
								if (table.find(m) != table.end() && table[m] != (string)"s" + to_string(closureList[i].go[next])) {
									cout << "该文法不是LR(1)文法，存在多重定义入口！" << endl;
									cout << "状态" << i << "+" << "符号" << next << "->" + (string)"s" + to_string(closureList[i].go[next]) << endl;
									cout << "状态" << i << "+" << "符号" << next << "->" + table[m] << "\t二者冲突" << endl;
									cout << "移进优先处理后，采用：" "状态" << i << "+" << "符号" << next << "->" + (string)"s" + to_string(closureList[i].go[next]) << endl;
									//return 0;
									table[m] = (string)"s" + to_string(closureList[i].go[next]);
								}
								else table[m] = (string)"s" + to_string(closureList[i].go[next]);
							}
							else { //形如 【X->α·Yβ，γ】,令table[i,Y]=j
								map<string, GRAM_ELEMENT_TYPE> m;
								m[to_string(i)] = next;
								if (table.find(m) != table.end() && table[m] != to_string(closureList[i].go[next])) {
									cout << "该文法不是LR(1)文法，存在多重定义入口！" << endl;
									cout << "状态" << i << "+" << "符号" << next << "->" + to_string(closureList[i].go[next]) << endl;
									cout << "状态" << i << "+" << "符号" << next << "->" + table[m] << "\t二者冲突" << endl;
									//return 0;
								}
								else table[m] = to_string(closureList[i].go[next]);
							}
						}
						break;
					}
				}
			}
		}
		return 1;
	}

	int  LR1TableGenerator::check(int time,list<GRAM_ELEMENT_TYPE>sentence, list<WORD> tokenList) {//
		//list<int> sentence; //需要分析的语句
		//int temp;
		//while (cin >> temp) {
		//	//if (temp > 2147483647 || temp < -2147483648) return 0;
		//	sentence.push_back(temp);
		//}
		for (auto it : sentence) {
			cout << it<<" ";
		}
		fstream f("sentence_" + to_string(time) + ".txt", ios::out); //分析过程输出到该文件
		if (!f) {
			cout << "无法打开文件sentence.txt" << endl;
		}
		f << "步骤\t\t状态栈\t\t符号栈\t\t输入串\t\t动作说明" << endl;
		vector<string> status; //状态栈
		vector<int> symbol; //符号栈   
							WORD tokenEnd = { (WORDTYPE)10 ,L"" };
							vector<WORD> tokenStack;//同步TOKEN
		int step = 1; //步骤数
		if (sentence.front() != CHAR_END || sentence.back() != CHAR_END || sentence.size() < 2) {
			cout << "语句应以" << CHAR_END << "开头，并以" << CHAR_END << "结束" << endl;
			return 0;
		}
		symbol.push_back(CHAR_END);       tokenStack.push_back(tokenEnd);
		sentence.erase(sentence.begin());   tokenList.erase(tokenList.begin());//同步token
		status.push_back("0");
		while (1) {
			f << step++ << "\t\t"; //输出步骤数
			for (unsigned int i = 0; i < status.size(); i++) //输出状态栈
				if (i == 0) f << status[i];
				else f << " " << status[i];
			f << "\t\t";
			for (unsigned int i = 0; i < symbol.size(); i++) //输出符号栈
				if (i == 0) f << symbol[i];
				else f << " " << symbol[i];
			f << "\t\t";
			{int i = 0;
			for (auto it : sentence) //输出输入串
				if (i == 0) f << it;
				else f << " " << it;
			i++;
			}
			f << "\t\t";
			string cur_status = status[status.size() - 1]; //当前状态
			int cur_symbol = sentence.front(); //当前“展望”字符
			string new_status; //下一入栈的新状态
			map<string, GRAM_ELEMENT_TYPE> m;
			m[cur_status] = cur_symbol;
			new_status = table[m];
			if (new_status == "acc") {
				cout << "分析成功，该语句合法！(具体分析过程请查看文件sentence_" << time << ".txt）" << endl << endl;
				f << "acc：分析成功" << endl;
				return 1;
			}
			else if (new_status[0] == 's') { //形如 table[i,b]=sj，状态sj入栈，并读入一个字符
				status.push_back(new_status.substr(1)); //入栈的状态要去掉第一个字符‘s’
				symbol.push_back(cur_symbol); //读入一个字符
											tokenStack.push_back(tokenList.front());
				sentence.erase(sentence.begin());     tokenList.erase(tokenList.begin());//同步token
				f << "ACTION[" << cur_status << "," << cur_symbol << "]=" << new_status << "，即状态" << new_status << "入栈" << endl;
			}
			else if (new_status[0] == 'r') { //形如 table[i,b]=rj，用产生式G(j)归约，且table[x,y]入栈
				new_status = new_status.substr(1); //去掉‘r’
				f << "r" << new_status << "：用";
				int gid = atoi(new_status.c_str()); //计算产生式编号
				//---------------------------------------------------------------------------------
				transDebug(gid,tokenList.back());
				//---------------------------------------------------------------------------------
				int len = gramList[gid].size() - 1; //被归约的字符串长度
				int reduced_symbol = gramList[gid][0]; //归约得到的非终结符
				//---------------------------------------------------------------------------------
				if (gramList[gid][1] != CHAR_NULL)
				{
					//---------------------------------------------------------------------------------
					for (int i = 0; i < len; i++) {
						status.pop_back(); //归约，即去掉栈顶的len个状态项
						symbol.pop_back(); 
												tokenStack.pop_back();
					}
					//---------------------------------------------------------------------------------
				}
				//---------------------------------------------------------------------------------

				map<string, GRAM_ELEMENT_TYPE> m;
				m[status[status.size() - 1]] = reduced_symbol;
				new_status = table[m];
				status.push_back(new_status);
				symbol.push_back(reduced_symbol);
												tokenStack.push_back(tokenEnd);//占位
				for (unsigned int i = 0; i < gramList[gid].size(); i++) {
					if (i == 1) f << "->";
					f << gramList[gid][i];
				}
				f << "归约，且GOTO[" << status[status.size() - 2] << "," << reduced_symbol << "]=" << new_status << "入栈" << endl;
			}
			else {
				cout << "该语句有语法错误！（详情请查看分析过程文件sentence_" << time << ".txt）" << endl << endl;
				return 0;
			}
		}
		f.close();
		cout << "该语句有语法错误！（详情请查看分析过程文件sentence_" << time << ".txt）" << endl << endl;
		return 0;
	}

	void LR1TableGenerator::transDebug(int x,WORD token) {
		if (x < gramListSN.size())

			cout << endl << gramListSN[x]<<"\t";
		else
			cout << endl << -1;
	}

	void LR1TableGenerator::initialize() {
		//LR1TableGeneratorNameSpace::LR1TableGenerator a;
		//初始化语义动作代码
		gramListSN.push_back(0);//增广文法产生式
		gramListSN.push_back(0);//程序->外部声明 外部声明星
		gramListSN.push_back(0); gramListSN.push_back(0);	//外部声明星->外部声明 外部声明星 | ~
		gramListSN.push_back(0); gramListSN.push_back(0);	//外部声明->函数定义 | "global" 声明

		gramListSN.push_back(0);	//函数定义->返回类型  函数名  复合语句
		gramListSN.push_back(48);	//返回类型->类型 48
		gramListSN.push_back(52);	//函数名->函数标识符 "(" 函数参数 ")" 52
		gramListSN.push_back(49);	//函数标识符->"标识符" 49
		gramListSN.push_back(0); gramListSN.push_back(0);	//函数参数->函数参数声明 逗号函数参数声明星 | ~
		gramListSN.push_back(0);	//函数参数声明->参数类型 参数名
		gramListSN.push_back(50);	//参数类型->类型 50
		gramListSN.push_back(51);	//参数名->对象 51
		gramListSN.push_back(0); gramListSN.push_back(0);	//逗号函数参数声明星->"," 函数参数声明 逗号函数参数声明星 | ~

		gramListSN.push_back(54);	//函数调用->调用函数名 "(" 调用参数 ")"
		gramListSN.push_back(55);	//调用函数名->"标识符" 55
		gramListSN.push_back(0); gramListSN.push_back(0);	//调用参数->参数 逗号参数星 | ~
		gramListSN.push_back(0); gramListSN.push_back(0);	//逗号参数星->"," 参数 逗号参数星 | ~
		gramListSN.push_back(53);	//参数->第一式 53

		gramListSN.push_back(0);//复合语句->"{" 语句星"}"
		gramListSN.push_back(0); gramListSN.push_back(0);//	语句星->语句 语句星 | ~

		gramListSN.push_back(0);//	循环内复合语句->"{" 循环内语句星 "}"
		gramListSN.push_back(0); gramListSN.push_back(0);//	循环内语句星->循环内语句 循环内语句星 | ~

		gramListSN.push_back(0);//	声明->类型 变量定义 逗号变量定义星 ";"
		gramListSN.push_back(0); gramListSN.push_back(0);//	逗号变量定义星->"," 变量定义 逗号变量定义星 | ~

		gramListSN.push_back(1); gramListSN.push_back(2);//	变量定义->对象 1 | 对象 "=" 初值 2

		gramListSN.push_back(3); gramListSN.push_back(4);//	对象->对象 "[" 常数式 "]" 3 | "标识符"4

		gramListSN.push_back(5); gramListSN.push_back(5); gramListSN.push_back(5); gramListSN.push_back(5); gramListSN.push_back(5);//	类型->"double"5 | "char"5 | "float"5 | "int"5 | "void"5


		gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0);//	循环内语句->声明 | 循环内复合语句 | 表达式语句 | 分支语句 | 循环语句 | 返回语句 | 循环内跳转语句

		gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(0);//	语句->声明 | 复合语句 | 表达式语句 | 分支语句 | 循环语句 | 返回语句

		gramListSN.push_back(0); gramListSN.push_back(0);//	表达式语句->第一式 ";" | ";"

		gramListSN.push_back(8); gramListSN.push_back(10);//	分支语句->"if语义一" "if语义二" 语句 8 | "if语义一" "if语义二" 语句 "if语义三" 语句 10
		gramListSN.push_back(6);//	"if语义一"->"if" 6
		gramListSN.push_back(7);//	"if语义二"->"(" 第一式 ")" 7
		gramListSN.push_back(9);//	"if语义三"->"else" 9

		gramListSN.push_back(13); gramListSN.push_back(15); gramListSN.push_back(21);//	循环语句->"while语义一" "while语义二" 循环内语句 13 | "while语义三" 循环内语句 "while" "(" 第一式 ")" ";" 15 | "for语义一" "for语义二" "for语义三" "for语义四" "for语义五" 循环内语句 21
		gramListSN.push_back(11);//	"while语义一"->"while" 11
		gramListSN.push_back(12);//	"while语义二"->"(" 第一式 ")" 12
		gramListSN.push_back(14);//	"while语义三"->"do"  14
		gramListSN.push_back(16);//	"for语义一"->"for" 16
		gramListSN.push_back(17);//	"for语义二"->"(" 第一式选";" 17
		gramListSN.push_back(18);//	"for语义三"->第一式选";" 18
		gramListSN.push_back(19);//	"for语义四"->第一式选 19
		gramListSN.push_back(20);//	"for语义五"->")" 20

		gramListSN.push_back(0); gramListSN.push_back(0);//	第一式选->第一式 | ~

		gramListSN.push_back(22); gramListSN.push_back(23);//	循环内跳转语句->"continue" ";" 22 | "break" ";" 23

		gramListSN.push_back(24);//	返回语句->"return" 第一式选 ";" 24


		gramListSN.push_back(0); gramListSN.push_back(0);//	第一式->第二式 | 对象 算符一 第一式

		gramListSN.push_back(0); gramListSN.push_back(0);//	第二式->第三式 | 第一式 "?" 第一式 ":" 第二式

		gramListSN.push_back(0); gramListSN.push_back(25);//	第三式->第四式 | 第三式 "||" 第四式 25

		gramListSN.push_back(0); gramListSN.push_back(26);//	第四式->第五式 | 第四式 "&&" 第五式 26

		gramListSN.push_back(0); gramListSN.push_back(27); gramListSN.push_back(28);//	第五式->第六式 | 第五式 "==" 第六式 27 | 第五式 "!=" 第六式 28

		gramListSN.push_back(0); gramListSN.push_back(29); gramListSN.push_back(30); gramListSN.push_back(31); gramListSN.push_back(32);//	第六式->第七式 | 第六式 "<" 第七式 29 | 第六式 ">" 第七式 30 | 第六式 "<=" 第七式  31 | 第六式 ">=" 第七式 32

		gramListSN.push_back(0); gramListSN.push_back(33); gramListSN.push_back(34);//	第七式->第八式 | 第七式 "+" 第八式  33 | 第七式 "-" 第八式 34

		gramListSN.push_back(0); gramListSN.push_back(35); gramListSN.push_back(36); gramListSN.push_back(37);//	第八式->第九式 | 第八式 "*" 第九式 35 | 第八式 "/" 第九式 36 | 第八式 "%" 第九式 37

		gramListSN.push_back(0); gramListSN.push_back(38);//	第九式->第十式 | "(" 类型 ")" 第九式 38

		gramListSN.push_back(0); gramListSN.push_back(39); gramListSN.push_back(40); gramListSN.push_back(41); gramListSN.push_back(42); gramListSN.push_back(43);//	第十式->第十一式 | "++" 对象 39 | "--" 对象 40 | 算符十 第九式 41 | "sizeof" 第十式 42 | "sizeof" "(" 类型 ")" 43

		gramListSN.push_back(0); gramListSN.push_back(0); gramListSN.push_back(44); gramListSN.push_back(45);//	第十一式->第十二式 | 对象 | 对象 "++" 44 | 对象 "--" 45

		gramListSN.push_back(46); gramListSN.push_back(46); gramListSN.push_back(46); gramListSN.push_back(46); gramListSN.push_back(0);//	第十二式-> "常数" 46 | "字符串" 46 | "字符" 46 | "(" 第一式 ")" | 函数调用

		gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47);//	算符一-> "=" 47 | "*=" 47 | "/=" 47 | "%=" 47 | "+=" 47 | "-=" 47

		gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47); gramListSN.push_back(47);//	算符十-> "&" 47 | "*" 47 | "+" 47 | "-" 47 | "!" 47



		gramListSN.push_back(0);//	常数式->第二式

		gramListSN.push_back(0); gramListSN.push_back(0);//	初值->第一式 | "{" 初值 逗号初值星 "}"
		gramListSN.push_back(0); gramListSN.push_back(0);//	逗号初值星->"," 初值 逗号初值星 | ~


		//获取LR1分析表
		
		getGram(translator);
		showGram();

		generateFirst();
		showFirst();

		generateClosure();
		outputClosure();

		generateTable();
		outputLR1Table();
	}

	void LR1TableGenerator::parser(int xxxxx) {
		std::wcout.imbue(std::locale("chs"));
		std::wcin.imbue(std::locale("chs"));//对wstring的输入输出设定中文环境
		OLEX lex;
		initialize();
		WORD token;
		wchar_t t;

		int time = 1;
		while (true) {
			long long unsigned pos = 0;
			list<LR1TableGeneratorNameSpace::GRAM_ELEMENT_TYPE> sentence;
			list<WORD> tokenList;
			sentence.push_back(CHAR_END);
			WORD tokenEnd = { (WORDTYPE)10 , L"" };
			tokenList.push_back(tokenEnd);
			//tokenList.push_back(lex.Analyse(L"#", pos,true));//占位
			//pos = 0;
			wcin.clear();
			wstring stringIn, stringLine;
			while (getline(wcin, stringLine)) {
				stringIn = stringIn + L" " + stringLine;
			};
			wcout << stringIn;
			while (pos < stringIn.size()) {
				token = lex.Analyse(stringIn, pos, true);
				long long unsigned test = translator.Trans(token);
				sentence.push_back(test);
				tokenList.push_back(token);
			}
			sentence.push_back(CHAR_END);
			tokenList.push_back(tokenEnd);//占位
			check(time++, sentence, tokenList);//
		}
		getchar();
	}
}

